{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "19095b39-daba-4632-8b23-35b22ab71a8c",
   "metadata": {
    "tags": []
   },
   "source": [
    "# 快速傅里叶变换fft\n",
    "具体要求参考[链接](https://www.wolai.com/zzutai/ne85AbnL15kmZPPJRQ2q4j)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "4e42cc3e-b29d-463d-aa51-5a1dae08a51b",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAABDAAAAFgCAYAAABNIolGAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMywgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/MnkTPAAAACXBIWXMAAAsTAAALEwEAmpwYAAAxlUlEQVR4nO3dfbRkZ10n+u+vT3eSTjfQwTSRxNHIkOkZFCIvM5IryomCEcS1Io7C6Mzo6L3h8uIMvkSIZGYUWaDGUUfUSJThJWggIrZRlDCIB6OGl8SQBPD2QhkMNkEM5CR0aJLO6ef+UXWSyuk6L11V3bVP9eezVq2u2vXs2k/9TtXev/7Vs59drbUAAAAAdNmWaXcAAAAAYD0KGAAAAEDnKWAAAAAAnaeAAQAAAHSeAgYAAADQeQoYcIKrvmn3Y5Kqam7F41NWLgMANpfNmq/IS2ByFDDgBFNVc1W1bWDRo5L8U1U9fkjbX6uqn1nn9b62qlpV/csNbPvkqto+ZPkdVfXsgcenDEtS+n3fMfB4a1WdO2RTb6mqnxx4/H8n+XBVnbxeHwFgFlXVb1XVR6fdj2VVdeZqBYmqekZV/VVVfdmKp/5zVf1JVZ20xuvKS2CGKWDADKiql/cP1uvektyf5MUDqz86yalJ/r8Vr7kzyfcnuXOdzR/s/3tvf73fXWPbX0rymiGv8cX+c4OveXiVvh+oql39ds9P8ldV9U0rXu91SV4xkBy9MMlrW2v3rvNeAGBWHUzy+dWerKqvXHHcfUl/+TdU1eGqWhy4HaiqA2u81vaqelRVPbaq/q+q+u6qemlV/VJV/VFVfTLJ/iT/7yov8bVJHtFa+9yK5ecnuae1dt867zORl8BM2jrtDgATcW+Sm1trXze4sKp+NckftdbeNbBsa5LBXxG+Osm+1tqhFa/5kiQfT/I/++t9R2vtD4dse6n/b+v/e0+S30hyyZC2cwPtU1UX9PtycpKn9H9R+Zsk25Pc21prgyv3h1tu728jrbW3VNXTklxTVeck+a0kT0kvobg/yV/1t/kVSf5rVV2a5KQk/7q19qkh/QOATa//y/7hJPcPHEuX8tBj8NYk25Ic7v9HerkocFqS306ynBd8KcltrbWzB9ad77cZtu3nJvm9/uvd3b/9Y5LPJPl0kr9IclV6BYxPrvIWvibJ3hWvuyvJBUl+pr/9ZZ9qrf3dwGN5CcwwBQyYDW3lgqo6Jb0hilc+pGFr9/eff2x6vwh8eZLTq+qP+k1+NsnHkrw0yXNaa0tV9a+SXFVVP9Zae11//ZOSPDLJI/rr7aqq09M7iB9Kb4TXXB5MgLYkOXXFAfqaJH+YZEeSb05yUZKfa639ZlX9bT+5GvS51tqTVyz74SS/2Vr7p6p6QZJvSfI7Sf4syRuTLCT5P621f1ZVL0zykST/cGQIAWBm/FyS/5IkK8986I8cGPQ/0zvm35ckrbXFqjqUBwsapyT5qiHrfXGVbVeSu1pru4620/3/0P/MwOPl0y6+JsnT+699Uf+WJKcn+fUkPyEvgRODU0hgxlTVW6vq3vR+6fhSkmsHhnzeX1XLQyW/kORd6f0icF3//jelt1+4Isn/aq3d0G+7L8l/TvIrVXVef9njktye5MP9xzcleXse/CXjvyX5bHqnoNyZ5HNJblvR3UNJfjzJHekVTv4iDyYWj0ryda21s/u/+swn2T3wPrdV1dbW2qHW2o0Dr/c/kvzbIXE5M8ll6Q09PaLgAwAz5GXpjSKYa61Va63SK1S8b+DxSen9R/3l/XUOr3iNliSttb9cXmfFbUeG25pkS1X9yw3cvraqvm5g3YNJ/jK9USCnJTm7v/xQeiNDf3o5L+jnBr+fBwst8hI4ARiBAbPnS0kub629dOUTVbWQ/jmhrbV/THJZVf2nJJcneV+SX0rvvNPvSvLZqvrB9ObHqCSL6RVFfq+fbNyc3j7knyX5P0n+eXpDQ38hvSTox5L8aGvtgYSoqk6qqlNaa8vnlT4wbHOIk9MrmCwnJjvTS7aWvTjJL/V/WXp7a+27W2ufq6ofSm9Y6kqnJbm0tfbXa2wTADa9jcyt0D91dOXpow9RVR9Pb66sw0ke1r/9apIL08sLTk/y6tbaqwdWOym9Y/b7N9DVrenlLaf3Hy+ld9rLYn/7y+3+n/RGV7x2xfrb0s9rIi+BE4ICBsymF1bVDwxZvjO9oYtJkurN7n1Okg+kNzzz7vTO13xYer9cfCLJ/tbawX77rUm+L8k/9X8tWBpILl6SXhIxl95BfOjQ1SR3Jdm1gffwrXnoXB3JQxOXX+vfXpHksdWbLfw30htZcqj/Xn8iyY8m+fv0hm/OVdWPpJdsvW4DfQCATaN6VxmbS3Lf4H/U11lna3r/ER92ZY8vpTcx5W3pFQiWJ8j85dbaT1XVG/PQyS6T3pwQ/9Ba+8qjfwerujrJHyT571X1J6219/aXb1vevrwETgwKGDAbBn+BSNYegTF46tjTk9zaWjtQVd+Q5EOttfuqarmIkSRnrDjYX91aa1X15Ul+MMl395fvSm+Y5MuSvDrJh5L8cnoJw8tba+fVkZc9Gzpksqrem+RJqzz3t621pyxPOtrv2/2ttT9OMslkCQA2m+9L8oZk6H/U01++2ukKPzJk2efSG3GR9P7TfUp6p1f8wMAPJR9asc7p6Z2qsTzx5lrua62tnEvj6UP6eEdr7ZP9UaOXJlkuYJyUB682Ii+BE4A5MGA2nJ4HL3d6SpL/svJSX/1k4Onp/TKy7BlJ7uj/+vLtSf60v/zV6Q2/HHab77e5N8kPJfnj/uNXttY+mt7kWf80sI2PJXlCP0n4jST/ceC54dlVryDz0v4EYG9M8sb+/ZemN4RzVVX14/XQS70N3u5Ya10A2OR+O71TP7cOzleR3siAdyU5beVcFukdV3emNyIgVfUbSc5Nktba/Io5J34rvauenT1w+7UVffjy9E7dSHpXH7lzjdsbhryHYXNgLHttkvMH5s04OQ+OAJGXwAlAAQNmw54kn0qS1trzB5KSr+4//9UDycrFA+u9Lb1zWz+Y5JlJfre//L4kbxqS5Cw/l9banf3t/uaKvpyegdm0W2sfT++XmIX0Jti6ZqDtavugtYa9rnV+atJLPj7cWts1eEvvfN1T1lkXADat/gSSB1trg5cG3ZPeHBKfSHJ3VX1FVb28qrb017mvtbZ8pY6kd+rFLUm2VdUHq+qOqvpkVS2mN0fW66pqf3/Z/qq6Z0U3vi7JR/v370ty/rBJQNObVHTYXB33t9YW+/Ng3LXi/d2c3iSdz+8v2p7kQP85eQmcABQwYJOr3ljFpyT56/7jR/UTjn+xot1LquoXa2BMaWvtfUmenAdn8P76/r8bOlC3/iVZB7axNb1fbT68Yp03JHl8kme11j47sHzwNLanJ/nG9M4VbUl+vZ8svTC9OT0W07tU2lBVtXzKy1qJxIbOBwaAWVBVj0iyN73/pL+kPy/GOeldkeMXVzQ/KXng2P6JJF9orf2b1trpefAyq3+V5G+SXNcffXHW4NVIqurU9E61uK6/aL3j7ijH5f+U5L/27+9Mb/6uDPT9AfISmD0KGLD5fX2Ss5L8cT9xuKq/fOWM19cl+XdJ3lhVcwPLH5veryU/meS3qupHs8o5oBtwbnqJxN+lPwyz36f3pfcLyUUr2v9VHhz6eU+S/5Xkj9KbcOtF/V8oLk9vTo9dSV60yna3pXd1lO9KLxl42sphmv3XlSgAcEKoqp3pFS8+m+Q/LF+qs7X2Z0mel+SH+8f8ZQ/MB9Fa+5HW2lv7r/OVSX4lvQkoF5O8Lsnjq+rlOdK/S+9Yu7D8UiN0fWtV7erPn/GIlU+21j68PN9EelcmuWtlmwHyEpgxJvGEze8V6Y2+uCe980Yrybekd1BfnnCqtdZurqpvSi+puDTJT1fVaUnemuQNrbVfqKq/Tm/Crh9M8v1V9f1rbbiqHpPk2f2HB9Ob5fut/Uk+H53e9dE/keQ96Z2X+gdVdVaSn2qtfb619i391zk5yS2ttXf3H29J75eOX05/zo7+ZGEnpZeEDNqR5HuS3JreqTBnJ/mL1tr8ir7OpzeDOQDMtKp6fJI3pzdC4SVJvqOqzkzyFf3b2emdMvILVfWPrbXfTnJ7Hjz1dPl1npbkLUne2Vp7Y1V9Z3ojMb4nyfuq6puT/Hx6k2qekeRVSd4yMDHnliR/ttqEounPuzFgW5JvyIPzeg0uX/keH53eDzj7B5bJS2DGGYEBm1g/GfnaJD+X5PPpTd4131r7XHqTUv1eko+nf3Dvn/f5jPSuY/6o9IoZu9IrgqS19t7++aVb0hvJcdqKW9L7FWLZ49K7vvpb+s9/Tx489/RfpPcrxo+31v59fzbuf5vkX+XI686vvHzbyen/0tFaO7l/25XeLx0rJ8vak94vKd/UWvtUv39P7Z+b+8AtvULNXABg9n1neqMrvyq9HOHC9H7Y+Gh6x+nvT+8/8/87yRVV9ZWttftba59cfoGqelGSP0/y7vQKAUn/eN2fHPOb0iuGvCW94sUX0hul8dMD/Tg5a8+B8fAV/T45yfsG2jwivaufPFABqar/VlXXpTcZ56+11j4xsL68BGZc9UeTAZtU//zOpbbiy9wfXXF6kr9d+Vz/+e3pHeB/rrX2wRXPXZFegvIDK5a3JM9urf1J//HyBGCH+48ftXwuaVXtSPKI1tqnc5T6hZm7W2sHNtB2VwYuw1ZVFyd5emvtOSvazSd5T2vNyDMAZlpVPTLJE5P8ZWvtS2u0+7Ikj2qt/c2Q5yrJv2+tXTmw7E+T/H5r7Vf7j09J8oSVecRA+69K8o9r9eFoVdXj0rvSyYdaa19Y8Zy8BGacAgZwhP75oWlHXpsdAABgKhQwAAAAgM4zBwYAAADQeQoYAAAAQOd1ZtKYXbt2tcc+9rHT7samd88992THjh3T7samJoaTIY7jE8PJEMfx3XjjjXcnub619m3T7svRkFuMz/dnMsRxfGI4GeI4GeI4vhtvvPGO1truo12vMwWMM844IzfccMO0u7HpLSwsZH5+ftrd2NTEcDLEcXxiOBniOL6q+vhmK14kcotJ8P2ZDHEcnxhOhjhOhjiOr6r+fpT1nEICAAAAdJ4CBgAAANB5ChgAAABA5607B0ZVPSLJW5PMJbknyfOSXJ7kcUne2Vp71Rrrvn4j7Ta7vTftz2XX7sunFw/mzF3bc/EFe3LhE8+adrcAmDLHhyPJKwCAUW1kBMb3JfnF1tq3JvlMkucnmWutnZfkMVV1zrCVquq5G2m32e29aX8uecet2b94MC3J/sWDueQdt2bvTfun3TUApsjxYVXyCgBgJNVa23jjqrcneXiSX26t/XFVPT/J9tbaG4a0/ZUk71qrXVVdlOSiJNm9e/eTr7766jHeynT82MIX87kvHRnDLzul8j/mTz3u/Tlw4EB27tx53Lc7S8RwMsRxfGI4GdOKY9eOD+M4//zzb2ytPWXSrzvpvKLfbtPnFl1iPzQZ4jg+MZwMcZwMcRzfqLnFhi+jWlXnJTktySeTLP989PkkT1pllR3rtWutXZHkiiTZs2dP24yXovn8u945fPmX2lQureOSPuMTw8kQx/GJ4WRMK45dOz50zbHIK5LZyC26xH5oMsRxfGI4GeI4GeI4PRuaxLOqHpnktUl+MMmBJNv7T+1c4zU22m5TO3PX9qNaDsCJwfFhdfIKAGAU6x78q+qkJL+b5JLW2t8nuTHJ0/pPn5veLyfDbLTdpnbxBXuyfdvcQ5Zt3zaXiy/YM6UeAdAFjg/DySsAgFFt5BSSH0pvmOYrquoVSd6Q5D9U1ZlJnpXkqVX1uCTf21q7dGC9vUmuG2w30Z53xPJs8j/x9lty39LhnGWWeQDi+LAGeQUAMJJ1CxittcvTu7zZA6rqmiTPTPLzrbW7ktyV5NIV691dVfMr2s2kC594Vq764G1Jkre94Lwp9waArnB8OJK8AgAY1YYn8RzUWrszybrTem+0HQBw4pJXAAAbYQIsAAAAoPMUMAAAAIDOU8AAAAAAOk8BAwAAAOg8BQwAAACg8xQwAAAAgM5TwAAAAAA6TwEDAAAA6DwFDAAAAKDzFDAAAACAzlPAAAAAADpPAQMAAADoPAUMAAAAoPMUMAAAAIDOU8AAAAAAOk8BAwAAAOg8BQwAAACg8xQwAAAAgM5TwAAAAAA6TwEDAAAA6DwFDAAAAKDzFDAAAACAzlPAAAAAADpPAQMAAADoPAUMAAAAoPMUMAAAAIDO21ABo6rOqKrr+vdfWFUL/duHq+p1q6yztapuG2j7+El2HADYvOQWAMDR2rpeg6o6LcmbkuxIktba5Uku7z/32v5zwzwhyVWttZdNpqsAwCyQWwAAo9jICIylJM9Lcvfgwqo6K8kZrbUbVlnvqUmeU1UfrKrXV9W6xRIA4IQgtwAAjlq11jbWsGqhtTY/8PjVSf53a+3PVmn/r5P8Q2vt9qp6c5K3t9auWdHmoiQXJcnu3buffPXVV4/2LjrgNR84mCS55Ou3T7UfBw4cyM6dO6fah81ODCdDHMcnhpMx7Th25fgwjvPPP//G1tpTJv26covum/b3Z1aI4/jEcDLEcTLEcXyj5hYj/XJRVVuSnJ/kFWs0u6W1dm///g1JzlnZoLV2RZIrkmTPnj1tfn5+lO50wuX7rk+SzM+fN9V+LCwsZDPHsQvEcDLEcXxiOBnTjmNXjg9dJ7fopml/f2aFOI5PDCdDHCdDHKdn1KuQfGOSD7S1h29cWVXnVtVckguT3DzitgCA2Se3AADWNGoB44Ikf778oKoeV1WvWtHmlUmuTPLhJNe31t4z4rYAgNkntwAA1rThU0gGz1Ftrf3kiuc+luTSFcs+kt5s4QAAR5BbAABHY9QRGAAAAADHjQIGAAAA0HkKGAAAAEDnKWAAAAAAnaeAAQAAAHSeAgYAAADQeQoYAAAAQOcpYAAAAACdp4ABAAAAdJ4CBgAAANB5ChgAAABA5ylgAAAAAJ2ngAEAAAB0ngIGAAAA0HkKGAAAAEDnKWAAAAAAnaeAAQAAAHSeAgYAAADQeQoYAAAAQOcpYAAAAACdp4ABAAAAdJ4CBgAAANB5ChgAAABA5ylgAAAAAJ2ngAEAAAB0ngIGAAAA0HkKGAAAAEDnKWAAAAAAnaeAAQAAAHTehgoYVXVGVV3Xv7+1qm6rqoX+7fFrrPf6qrq+qi6dVIcBgM1PbgEAHK11CxhVdVqSNyXZ0V/0hCRXtdbm+7dbV1nvuUnmWmvnJXlMVZ0zqU4DAJuX3AIAGEW11tZuUPXwJJXkD1pr81X1oiQvTnJPkluTvKC1dv+Q9X4lybtaa39cVc9Psr219oYVbS5KclGS7N69+8lXX331JN7TVLzmAweTJJd8/fap9uPAgQPZuXPnVPuw2YnhZIjj+MRwMqYdx64cH8Zx/vnn39hae8qkXk9usXlM+/szK8RxfGI4GeI4GeI4vlFzi63rNWit3Z0kVbW86ENJntFau72q3pzk2UmuGbLqjiT7+/c/n+RJQ177iiRXJMmePXva/Pz8UXa/Oy7fd32SZH7+vKn2Y2FhIZs5jl0ghpMhjuMTw8mYdhy7cnzoErnF5jHt78+sEMfxieFkiONkiOP0rFvAGOKW1tq9/fs3JFlt+OaBJMs/N+2MCUMBgOHkFgDAukY58F9ZVedW1VySC5PcvEq7G5M8rX//3CSfHGFbAMDsk1sAAOsaZQTGK5P8Tnrnrl7TWntPVT0uyfe21gZnBN+b5LqqOjPJs5I8ddzOAgAzSW4BAKxrwwWM1tp8/9+PpDdb+OBzH0ty6Ypld1fVfJJnJvn51tpdY/YVAJghcgsA4GiMMgJjw1prdyYx/TcAMBFyCwA4cZn8CgAAAOg8BQwAAACg8xQwAAAAgM5TwAAAAAA6TwEDAAAA6DwFDAAAAKDzFDAAAACAzlPAAAAAADpPAQMAAADoPAUMAAAAoPMUMAAAAIDOU8AAAAAAOk8BAwAAAOg8BQwAAACg8xQwAAAAgM5TwAAAAAA6TwEDAAAA6DwFDAAAAKDzFDAAAACAzlPAAAAAADpPAQMAAADoPAUMAAAAoPMUMAAAAIDOU8AAAAAAOk8BAwAAAOg8BQwAAACg8xQwAAAAgM7bUAGjqs6oquv69x9RVX9SVe+uqt+vqpNWWWdrVd1WVQv92+Mn2XEAYPOSWwAAR2vdAkZVnZbkTUl29Bd9X5JfbK19a5LPJPm2VVZ9QpKrWmvz/dutk+gwALC5yS0AgFFUa23tBlUPT1JJ/qC1Nr/iubcn+YXW2vuHrPeiJC9Ock+SW5O8oLV2/4o2FyW5KEl279795Kuvvnr0dzJlr/nAwSTJJV+/far9OHDgQHbu3DnVPmx2YjgZ4jg+MZyMacexK8eHcZx//vk3ttaeMqnXk1tsHtP+/swKcRyfGE6GOE6GOI5v1Nxi63oNWmt3J0lVPWR5VZ2X5LRhCUbfh5I8o7V2e1W9Ocmzk1yz4rWvSHJFkuzZs6fNz88fbf874/J91ydJ5ufPm2o/FhYWspnj2AViOBniOD4xnIxpx7Erx4cukVtsHtP+/swKcRyfGE6GOE6GOE7PugWMYarqkUlem+S71mh2S2vt3v79G5KcM8q2AIDZJ7cAANZz1Fch6U+s9btJLmmt/f0aTa+sqnOrai7JhUluHq2LAMAsk1sAABsxymVUfyjJk5K8oj8D+POq6nFV9aoV7V6Z5MokH05yfWvtPeN1FQCYUXILAGBdGz6FZHmSrdba5UkuH9Lk0hXtP5LebOEAAEeQWwAAR2OUERgAAAAAx5UCBgAAANB5ChgAAABA5ylgAAAAAJ2ngAEAAAB0ngIGAAAA0HkKGAAAAEDnKWAAAAAAnaeAAQAAAHSeAgYAAADQeQoYAAAAQOcpYAAAAACdp4ABAAAAdJ4CBgAAANB5ChgAAABA5ylgAAAAAJ2ngAEAAAB0ngIGAAAA0HkKGAAAAEDnKWAAAAAAnaeAAQAAAHSeAgYAAADQeQoYAAAAQOcpYAAAAACdp4ABAAAAdJ4CBgAAANB5ChgAAABA5ylgAAAAAJ23ddodYDL23rQ/l127L/sXD+as9783F1+wJxc+8axpdwtgauwXYXS+PwBHsm+cvg2NwKiqM6rquoHHr6+q66vq0nXW21A7xrP3pv255B23Zv/iwSTJ/sWDueQdt2bvTfun3DOA6bBf7D65RXf5/gAcyb6xG9YtYFTVaUnelGRH//Fzk8y11s5L8piqOmeV9TbUjvFddu2+HDy09JBlBw8t5bJr902pRwDTZb/YbXKLbvP9ATiSfWM3bOQUkqUkz0vyB/3H80mu7t9/d5KnJfn4kPXWbVdVFyW5KEl2796dhYWFDXe8axb7lbhpvIflKuCw5Zs5ptNy4MABcZsAcRyfGI6uS/vFaR4fOkxu0WFd+v7MCvvz8YnhZIjj6Owbu2HdAkZr7e4kqarlRTuSLI+T+XySJ62y6rrtWmtXJLkiSfbs2dPm5+c32O3uuXzf9UmS+fnzjvu2z3r/e4d+oc7atT2bOabTsrCwIG4TII7jE8PRdWm/OM3jQ1fJLbqtS9+fWWF/Pj4xnAxxHJ19YzeMchWSA0m29+/vXOM1NtqOMV18wZ5s3zb3kGXbt83l4gv2TKlHANNlv7jpyC06xPcH4Ej2jd0wyoH/xvSGbCbJuUk+OWY7xnThE8/Ka577+Jw01/tznrVre17z3MebERc4Ydkvbjpyiw7x/QE4kn1jN4xyGdW9Sa6rqjOTPCvJU6vqcUm+t7V26Vrtxuwra7jwiWflqg/elsXFxVz7sm+edncAps5+cVPZG7lFp/j+ABzJvnH6NjwCo7U23//37vQm0Xp/kvNba3e11j62IsEY2m5CfQYAZoDcAgA4GqOMwEhr7c48OAv42O0AgBOb3AIAWI/JrwAAAIDOU8AAAAAAOk8BAwAAAOg8BQwAAACg8xQwAAAAgM5TwAAAAAA6TwEDAAAA6DwFDAAAAKDzFDAAAACAzlPAAAAAADpPAQMAAADoPAUMAAAAoPMUMAAAAIDOU8AAAAAAOk8BAwAAAOg8BQwAAACg8xQwAAAAgM5TwAAAAAA6TwEDAAAA6DwFDAAAAKDzFDAAAACAzlPAAAAAADpPAQMAAADoPAUMAAAAoPMUMAAAAIDOU8AAAAAAOm/rKCtV1QuTPK//cFeSD7TWXrCizdYkn+jfkuSHW2u3jthPAGBGySsAgI0YqYDRWrs8yeVJUlWvTfKmIc2ekOSq1trLRu8eADDr5BUAwEaMdQpJVZ2V5IzW2g1Dnn5qkudU1Qer6vX9X04AAIaSVwAAaxn34P/i9H8xGeJDSZ7RWru9qt6c5NlJrhlsUFUXJbkoSXbv3p2FhYUxuzM9i4sHk2Sq72Fx8WCWlpY2dRy74MCBA2I4AeI4PjEcXxf2i104PmwiY+UVyWzlFtPWhe/PrLA/H58YToY4js++cbpGLmBU1ZYk5yd5xSpNbmmt3du/f0OSc1Y2aK1dkeSKJNmzZ0+bn58ftTtTd/m+65Mk8/PnTbUPi4uL2cxx7IKFhQUxnABxHJ8Yjq8L+8UuHB82g0nkFcls5RbT1oXvz6ywPx+fGE6GOI7PvnG6xjmF5BvTm2SrrfL8lVV1blXNJbkwyc1jbAsAmG3yCgBgTeMUMC5I8udJUlWPq6pXrXj+lUmuTPLhJNe31t4zxrYAgNkmrwAA1jTyKSSttZ8cuP+xJJeueP4j6c0YDgCwJnkFALCesa5CAgAAAHA8KGAAAAAAnaeAAQAAAHSeAgYAAADQeQoYAAAAQOcpYAAAAACdp4ABAAAAdJ4CBgAAANB5ChgAAABA5ylgAAAAAJ2ngAEAAAB0ngIGAAAA0HkKGAAAAEDnKWAAAAAAnaeAAQAAAHSeAgYAAADQeQoYAAAAQOcpYAAAAACdp4ABAAAAdJ4CBgAAANB5ChgAAABA5ylgAAAAAJ2ngAEAAAB0ngIGAAAA0HkKGAAAAEDnKWAAAAAAnaeAAQAAAHSeAgYAAADQeQoYAAAAQOcddQGjqrZW1W1VtdC/PX6Vdq+vquur6tLxuwkAzCq5BQCwEaOMwHhCkqtaa/P9260rG1TVc5PMtdbOS/KYqjpn3I4CADNLbgEArGvrCOs8Nclzqur8JLcmeUFr7f4VbeaTXN2//+4kT0vy8ZUvVFUXJbkoSXbv3p2FhYURutMNi4sHk2Sq72Fx8WCWlpY2dRy74MCBA2I4AeI4PjEcXxf2i104PmwCcosO6sL3Z1bYn49PDCdDHMdn3zhdoxQwPpTkGa2126vqzUmeneSaFW12JNnfv//5JE8a9kKttSuSXJEke/bsafPz8yN0pxsu33d9kmR+/ryp9mFxcTGbOY5dsLCwIIYTII7jE8PxdWG/2IXjwyYgt+igLnx/ZoX9+fjEcDLEcXz2jdM1SgHjltbavf37NyQZNoTzQJLt/fs7Y7JQAGB1cgsAYF2jHPyvrKpzq2ouyYVJbh7S5sb0hnYmyblJPjlS7wCAE4HcAgBY1ygjMF6Z5HeSVHrDOz9dVa9qrQ3OCL43yXVVdWaSZ6V3bisAwDByCwBgXUddwGitfSS92cIHXbqizd1VNZ/kmUl+vrV216gdBABmm9wCANiIUUZgbEhr7c48OFs4AMBY5BYAcGIzARYAAADQeQoYAAAAQOcpYAAAAACdp4ABAAAAdJ4CBgAAANB5ChgAAABA5ylgAAAAAJ2ngAEAAAB0ngIGAAAA0HkKGAAAAEDnKWAAAAAAnaeAAQAAAHSeAgYAAADQeQoYAAAAQOcpYAAAAACdp4ABAAAAdJ4CBgAAANB5ChgAAABA5ylgAAAAAJ23ddodADaXvTftz2XX7sunFw/mzF3bc/EFe3LhE886busDALNjEnmB3AJOHAoYwIbtvWl/LnnHrTl4aClJsn/xYC55x61JsqFEYdz1AYDZMYm8QG4BJxankAAbdtm1+x5IEJYdPLSUy67dd1zWBwBmxyTyArkFnFgUMIAN+/TiwaNaPun1AYDZMYm8QG4BJxYFDGDDzty1/aiWT3p9AGB2TCIvkFvAiUUBA9iwiy/Yk+3b5h6ybPu2uVx8wZ7jsj4AMDsmkRfILeDEYhJPYMOWJ8P6ibffkvuWDueso5zpe9z1AYDZMYm8QG4BJxYFDOCoXPjEs3LVB29LkrztBecd9/UBgNkxibxAbgEnjpEKGFX1iCRvTTKX5J4kz2ut3beizdYkn+jfkuSHW2u3jtFXAGAGySsAgI0YdQ6M70vyi621b03ymSTfNqTNE5Jc1Vqb798kGQDAMPIKAGBdI43AaK39+sDD3Uk+O6TZU5M8p6rOT3Jrkhe01u4fbFBVFyW5KEl2796dhYWFUbrTCYv9SzVN8z0sLh7M0tLSpo5jFxw4cEAM17GRz/tacezC92Uz8FkcXxf2iz7v65tUXpHMVm4xbV34/swK+/O1jZtXbPQ18FmcBPvG6RprDoyqOi/Jaa219w95+kNJntFau72q3pzk2UmuGWzQWrsiyRVJsmfPnjY/Pz9Od6bq8n3XJ0nm56d33t3l+67P4uJiNnMcu2BhYUEM17GRz/tacezC92Uz8FkcXxf2iz7vGzduXpHMVm4xbV34/swK+/O1jZtXbPQ18FmcBPvG6Rq5gFFVj0zy2iTftUqTW1pr9/bv35DknFG3BQDMNnkFALCekebAqKqTkvxukktaa3+/SrMrq+rcqppLcmGSm0frIgAwy+QVAMBGjDoC44eSPCnJK6rqFUn+LMm21tqlA21emeR3klSSa1pr7xmrpwDArJJXAADrGnUSz8uTXL5Om4+kN2M4AMCq5BUAwEaMehlVAAAAgONGAQMAAADoPAUMAAAAoPMUMAAAAIDOU8AAAAAAOk8BAwAAAOi8kS6jChwbe2/an8uu3ZdPLx7Mmbu25+IL9uTCJ5417W6dcPwdAJgVjmnT528Ak6OAAR2x96b9ueQdt+bgoaUkyf7Fg7nkHbcmiYPcceTvAMCscEybPn8DmCynkEBHXHbtvgcObssOHlrKZdfum1KPTkz+DgDMCse06fM3gMlSwICO+PTiwaNazrHh7wDArHBMmz5/A5gsBQzoiDN3bT+q5Rwb/g4AzArHtOnzN4DJUsCAjrj4gj3Zvm3uIcu2b5vLxRfsmVKPTkz+DgDMCse06fM3gMkyiSd0xPJETj/x9lty39LhnGWW6qnwdwBgVjimTZ+/AUyWAgZ0yIVPPCtXffC2JMnbXnDelHtz4vJ3AGBWOKZNn78BTI5TSAAAAIDOU8AAAAAAOs8pJGPYe9P+XHbtvnx68WC2zW3Jru1b8w0/+958evFgznR+G8AJa/D4sKWSqspXv/ydjg0AAGNQwBjR3pv255J33JqDh5aSJPctHc5nD9z3wPP7Fw/mknfcmiQSVYATyMrjw1JL0loSxwYAgHE4hWREl12774HkdDUHDy3lsmv3HaceAdAF6x0fHBsAAEajgDGiTy8enGg7AGbDRvb7jg0AAEdPAWNEZ+7aPtF2AMyGjez3HRsAAI6eAsaILr5gT7Zvm1uzzfZtc7n4gj3HqUcAdMF6xwfHBgCA0ZjEcwwnb93ywHnOW7dUHnnqtnzunvt6E7YlOWXbsa8PrbwSyiNPPnzMtwmwmdx17+HjdoWo5X3y4BwYc5UHjgtzVQ+ZA8NEngAAG6eAMYKVM8wnyeH+DPNtoN2dXzx0TGebH3YllM98MTn75e/MWS7VB5ygVl7CdKkl+WJvzoljeRWQYceGLZWc/WU78g+LX8yhpZYlVyMBABiZU0iO0t6b9ufHrr75iBnmD7fkswfuy+H20PYHDy3lx66+OXtv2j/xvqw10/1ycnwstgvQVctFhP2LB9Py4MiHQcfqKiA//YcfHXps+NSdB3Pf/W3o8eGnrvnoxPsBADCrjMDYgOVf8/aPOGv8Umt56ds+nJe+7cM57dRt+e/f8TVj/+K296b96/ZnuXiS+IUPODEMKyIMM+r+fNDgsaHy0BF4g+5bWv3UvsWDh/KYS96Zwy1GzgEArEMBI70k9Keu+WgWDx5K0hvye7hlzYR0VHd+8dADxYxhhm17nP4MFk+WX0eSDMyClfvuo3X2y9+54X3uevvhtfbNJ81tyaGlw6u2WR6ZsX/x4AP762Hbtu8GAE50nSlgfPLuwzn75e984PGkkspR1llOJo+mWLClktN3nJQ77jnyNJKjMWzbo/RnrdceTJIHHcv4Hou/0zHd9rXvnNq2lyeE/bqffvfQ/5h1IVZzlVRVzn75OzNXlaXWhq/zruH/QRz2Hrv2Gakkc1tWf4/HLeZDPotdi1VXtj2Kje5zx9kP/7PTtucfFr+Ye+/f+NrDtj3NffdJZzz2yRvuPADAMVKtjZYGVtXrkzwuyTtba68atc2ykx99Tnv09//ySH3pgn9++o6c/rCTc8cX7s3f3XHPtLsDQAfMVfKUsx+Zj91+dw7et5T7x6lwT9Htb3pp7r3943UstzHpvCJ5MLc4UYt64xWqHyzc7jp1W+784qHOvO+uxWozbHv5h4f7D69fjD/+P4r0PmtzlTx8+5GftY1ue9z3eDy+T6u9xy58Rmx7468zV71lx/M9btZYrbXO/jeOlluMNIlnVT03yVxr7bwkj6mqc0ZpMyuWixdJcvrDTs7JWytbjvpPMb65KWwTgOG2VO8KJMu+6pGnTuXYsBkc67xilFE1kxqds1m3vTRwdbU7v3jouG57s8VqM2x7qeWBAurx6u/RftaW2vDP2ka3Pe57PB7fp9XeYxc+I7a98ddZasf/PW7WWK23zihGPYVkPsnV/fvvTvK0JB8foc0DvuILn82rr/v1EbszPVXJw07Z9pBl99x7f06a25Iv3b+UEQe4jGT7trneNpPVPy0AJ5LqFXeXWo7rfrGqcsrWLdm2tfc7wT333p8dJ2/NofsPb2iS0a75j8d+E/OZcF6RbN7cAgBm3ai5xagFjB1Jlq/P+fkkTxqlTVVdlOSiJHnMjoeP2JXp2LalcvqplUecVElWzDC/fXlgy1zuuq/ls/ccHnopv0nadUrly09NlpaSA0tbjss2AbpsbkvyqFO3ZOfc4eO2X3zosSF54PiwfcuD9/vHhju+2HJonJ8gZstE8opkc+cWAMDaRi1gHEiyvX9/Z4afirJum9baFUmuSHrnqb7sG180Yncma9g5O5O4/OlGLrl3tOciLc9Kf0G/XwsLC5mfn39ge+PM0A+wmazcL164gf3iOOd/rra9ozV4bFhzUtxp+sRLj/UWJpJXJN3NLQCAASPmFqMWMG5Mb+jm+5Ocm2TfiG1WdbwnFZlEgWI9Fz7xrON6+bth21urqLEZJ3+ZxW2fduq2fPsTHp0/uvn2zv6ddm3flqreeZzr/Ydro++xa3+nU7dtycnb5lZ9j7Pw+dxs/Z3Evvt474c3YiN9mva++zhUU455XgEAbH4jXYWkqh6e5Lokf5rkWUmen+S7W2uXrtHmqa21u1Z7zT179rR9++Qi4xr8pZHRiOFkiOP4xHAyxHF8VXVja+0px/D1J55XJK5CMomrJuzYmpx0UreumtC1WG2GbQ/+8HC8+nu0n7XV+rjRbY/7Ho/H9+lo+jipbW+Gz+dm2/au7dty//2HcuDQ8XuPmzVWa60z6lVIRhqB0Vq7u6rmkzwzyc+31j6T5OZ12tw1yrYAgNl2rPKKsx++Jft+9tsn3t8TiQLgZIjj+MRwMsRxMsRxfPWzz7lxlPVGPYUkrbU78+Bs4CO3AQCQVwAA6xk6ARYAAABAl4w0B8axUFVfiAm5JuH0JHdMuxObnBhOhjiOTwwnQxzHd06ST7XWvnbaHTkacouJ8P2ZDHEcnxhOhjhOhjiOb09r7WFHu9LIp5AcA/uO5QRhJ4qqukEcxyOGkyGO4xPDyRDHyaiqG6bdhxHILcbk+zMZ4jg+MZwMcZwMcRzfqHmFU0gAAACAzlPAAAAAADqvSwWMK6bdgRkhjuMTw8kQx/GJ4WSI42Rsxjhuxj53jRhOhjiOTwwnQxwnQxzHN1IMOzOJJwAAAMBqujQCAwAAAGAoBQwAAACg86ZSwKiqM6rquoHHW6vqtqpa6N8e31/++qq6vqounUY/u25lHPvLjoiZOK7PZ3CyxG00wz6HYrlxQ44t9ocjGIzjZto3yi0mQ24xOT6DkyNmo5FXjE9uMb5J5xXHvYBRVacleVOSHQOLn5DkqtbafP92a1U9N8lca+28JI+pqnOOd1+7bFgch8VMHDfMZ3BCxG0sD/kcJjknYrkhK/eJ9oejGXJs2RT7RrnFZMgtJs5ncALEbCzyijHILcZ3LPKKaYzAWEryvCR3Dyx7apLnVNUH+9WXrUnmk1zdf/7dSZ52XHvZfcPiOJ8jYzZsGUfyGZyc+YjbqB7yOUzyjIjlRq3cJ87H/nAUK+O4WfaNcovJkFtMls/gZMxHzEYlrxiP3GJ8E88rjnkBo6peNzBEZCHJS1trd61o9qEkz2it/Zsk25I8O70qzf7+859Pcsax7muXbTCOw2ImjkMMiefu+AxOiriNbuW+8FkRyw1prd29Yp9ofziCIXHs5PFZbjEZcovJklscM2I2OnnFGOQW4zsWecXWY9HRQa21F2yg2S2ttXv7929Ib3jTgSTb+8t25gSfcHSDcRwWM3EcYmU8q+pkn8GJEbfRrdwXfmfEclT2h5PRyeOz3GIy5BaTJbc4ZsRsdPKKybI/HN/Yx+auBPjKqjq3quaSXJjk5iQ35sHhI+cm+eR0urapDIuZOG6Mz+DkiNvoVn4OXxyxHJX94WRs5n3jZu57l/gujc5ncDLEbHTyismyPxzf2PvFYz4CY4NemeR3klSSa1pr76mqhye5rqrOTG+401On2cFNYm+OjFkbsowj+QxOzt6I26ge8jmMWI5jb+wPJ2Ez7xs3c9+7ZG98l0blMzgZeyNmo5JXTNbe2B+Oa+z9YrXWjn03R9SftfSZSf68tfaZafdnMxgWM3EcndiNRtwmRyxHZ3947GzmOG7mvk+L79Jkid3RE7PJEcvx2B8eG0cTw04XMAAAAACS7syBAQAAALAqBQwAAACg8xQwAAAAgM5TwAAAAAA6TwEDAAAA6Lz/Hw7QefsOZg/SAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 1080x360 with 2 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "import numpy as np  \n",
    "import matplotlib.pyplot as plt  \n",
    "import math  \n",
    "\n",
    "def draw_sin(amp, freq, phase, sampleList):\n",
    "    return amp * np.sin(-2 * math.pi * freq * sampleList + phase)\n",
    "def discard(arr, thresh, thresh1):\n",
    "    arr[thresh:thresh1]=0 \n",
    "    return arr \n",
    "strate = 3000\n",
    "t = np.linspace(0, 1, strate) \n",
    "sin1= draw_sin(amp=1.5, freq=30, phase=0, sampleList=t)\n",
    "sin2= draw_sin(amp=3, freq=5, phase=0, sampleList=t)\n",
    "sin3= draw_sin(amp=10, freq=100, phase=0, sampleList=t)\n",
    "sin4= draw_sin(amp=20,freq=120,phase=0,sampleList=t)\n",
    "m = sin1 + sin2 + sin3 + sin4\n",
    "\n",
    "fCoefs = np.fft.fft(m,strate)\n",
    "amp_list=2*np.abs(fCoefs/strate)\n",
    "freqs = np.fft.fftfreq(len(amp_list), 1/strate)\n",
    "#第一种去噪方式：利用掩膜去噪将振幅低于0.5的噪音去除\n",
    "mask=amp_list>1\n",
    "f=mask*amp_list\n",
    "#第二种去噪方式：将频率高于110hz的噪音去除\n",
    "f1=np.copy(f)\n",
    "f1=discard(f1,110,-110)\n",
    "amp_shifted=np.fft.fftshift(f1)\n",
    "freq_shift=np.fft.fftshift(freqs) \n",
    "#绘制图像\n",
    "fig,ax=plt.subplots(1,2,figsize=(10, 4)) \n",
    "ax[0].stem(freqs,amp_list)\n",
    "ax[0].set_xlim([-150,150])\n",
    "ax[0].set_ylim([-1, 25])\n",
    "ax[0].grid()\n",
    "ax[1].stem(freq_shift,amp_shifted)\n",
    "ax[1].set_xlim([-150,150])\n",
    "ax[1].set_ylim([-1, 20])\n",
    "ax[1].grid()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
